package com.剑指offer.第七章队列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 最近请求次数
 */
public class ReceterCounter {

    int windowsize = 3000;

    private Queue<Integer> queue = new LinkedList<>();

    public ReceterCounter() {

    }

    /**
     * 返回在[t-3000,t]之前的请求次数 t为毫秒 每次t都比之前的大  比t-3000小的 移出
     *
     * @param i
     * @return
     */
    private int ping(int i) {
        queue.offer(i);
        while (i - 3000 > queue.peek()) {
            queue.poll();
        }
        return queue.size();
    }


    /**
     * 使用队列遍历树，广度优先
     *
     * @param treeNode
     * @return
     */
    public List<Integer> bfs(TreeNode treeNode) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (treeNode != null) {
            queue.offer(treeNode);
        }

        ArrayList<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            result.add(poll.val);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return result;
    }

}
